﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <stdio.h>

/*
* 题目：复制带随即指针的链表
* 内容：给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
* 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。
* 新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。
* 复制链表中的指针都不应指向原链表中的节点 。
* 链接：https://leetcode-cn.com/problems/copy-list-with-random-pointer
* 
*/

/*
* 思路：
* 首先创建节点，复制原链表的节点并插入到该节点后。
* 根据节点的相对位置和原链表节点random对应关系找出插入节点间的random关系
* 提取出插入的节点，并还原原链表
*/
struct Node 
{
	int val;
	struct Node* next;
	struct Node* random;
};
struct Node* copyRandomList(struct Node* head) {
    struct Node* cur = head;
    // 1.创建节点并插入到链表中
    while (cur)
    {
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        copy->val = cur->val;
        copy->next = cur->next;
        cur->next = copy;
        cur = copy->next;
    }
    // 2.判断插入节点的random的对应值
    cur = head;
    while (cur)
    {
        struct Node* copy = cur->next;
        if (cur->random == NULL)
        {
            copy->random = NULL;
        }
        else
        {
            copy->random = cur->random->next;
        }
        cur = copy->next;
    }
    // 3.将插入的节点提取出来并且还原原链表
    cur = head;
    struct Node* copyHead = NULL;
    struct Node* tail = NULL;
    while (cur)
    {
        struct Node* copy = cur->next;
        struct Node* next = copy->next;
        if (tail == NULL)
        {
            tail = copyHead = copy;
            // 原链表连接
            cur->next = next;
            cur = next;
        }
        else
        {
            tail->next = copy;
            tail = tail->next;
            // 原链表连接
            cur->next = next;
            cur = next;
        }
    }
    return copyHead;
}